package com.github.tangmonkmeat;

import java.util.Arrays;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/8/19 下午4:23
 */
public class 无重叠区间 {

    public static void main(String[] args) {

        int res = eraseOverlapIntervals(new int[][]{{0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 6}});

        System.out.println(res);

    }


    public static int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        Interval[] its = new Interval[2 * n];
        for(int i = 0;i < n;i++){
            its[2 * i] = new Interval(intervals[i][0], 0);
            its[2 * i + 1] = new Interval(intervals[i][1], 1);
        }

        // 排序
        Arrays.sort(its,(a, b) -> {
            if(a.val < b.val){
                return -1;
            }else if(a.val > b.val){
                return 1;
            }else{
                // val相同，type=1的排前面
                return Integer.compare(b.type, a.type);
            }
        });

        // 以下代码用于查看排序好的intervals数组中的所有元素
        for (int d=0;d<2*n;d++){
            System.out.println("type: "+its[d].type+", val: "+its[d].val);
        }


        int max = 1;
        int count = 0;
        for(int i = 0;i < 2 * n;i++){
            if(its[i].type == 0){
                count++;
                max = Math.max(max,count);
            }else{
                count--;
            }
        }
        return max - 1;
    }

    static class Interval{
        int val;
        int type;
        public Interval(int val,int type){
            this.val = val;
            this.type = type;
        }
    }

}
